import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 56. Merge Intervals 合并区间
 * https://leetcode-cn.com/problems/merge-intervals/
 */
class MergeIntervals {
    /**
     * 方法：合并重叠区间
     * 
     * Args:
     *     intervals: 二维整数数组，表示多个区间，每个区间包含两个元素[start, end]
     * 
     * Returns:
     *     二维整数数组，表示合并后的不重叠区间
     * 
     * Time: O(nlogn)，其中n是区间数量，主要时间消耗在排序上
     * Space: O(logn)，排序所需的栈空间
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (p, q) -> p[0] - q[0]);
        List<int[]> ans = new ArrayList<>();
        for(int[] p : intervals){
            int m = ans.size();
            if(m > 0 && p[0] <= ans.get(m-1)[1]){
                ans.get(m-1)[1] = Math.max(ans.get(m-1)[1], p[1]);
            }else{
                ans.add(p);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}